package sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

//七大排序
public class SevenSort {
    private static ThreadLocalRandom random = ThreadLocalRandom.current();
    public static void main(String[] args) {
        int n = 10000000;
        int[] arr = SortHelper.generaRandomArray(n,0,Integer.MAX_VALUE);
        int[] arr1 = SortHelper.arrCopy(arr);
        int[] arr2 = SortHelper.arrCopy(arr);
        int[] arr3 = SortHelper.arrCopy(arr);
        int[] arr4 = SortHelper.arrCopy(arr);
        int[] arr5 = SortHelper.arrCopy(arr);
//        SortHelper.testSort(arr,"selectionSort");
//        SortHelper.testSort(arr2,"selectionSortOP");
//        SortHelper.testSort(arr3,"insertionSort");
//        SortHelper.testSort(arr1,"insertionSortBS");
//        SortHelper.testSort(arr4,"shellSort");
        SortHelper.testSort(arr5,"heapSort");
        SortHelper.testSort(arr2,"mergeSort");
        SortHelper.testSort(arr1,"quickSort");
        SortHelper.testSort(arr3,"quickSortHoare");
    }


    public static void selectionSort(int[]  arr){
        // 最开始无序区间[i...n)
        // 有序区间[]
        // 最外层的for循环指的循环走的趟数，每走一趟外层循环，就有一个最小值放在了正确的位置
        for (int i = 0; i<arr.length-1;i++) {
            // min指的是最小元素的索引下标
            int min = i;
            // 内层循环在查找当前无序区间的最小值索引
            for (int j = i+1; j < arr.length ; j++) {
                if (arr[j]<arr[min]){
                    // j对应的元素比当前最小值还小
                    min=j;
                }
            }
            // min这个变量一定保存了当前无序区间的最小值索引
            // 有序区间[0..i) + 1
            // 无序区间[i..n) - 1
            swap(arr,i,min);
        }
    }


    /**
     * 双向选择排序
     * @param arr
     */
    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high= arr.length-1;
        // low == high => 无序区间只剩下最后一个元素，其实整个数组已经有序了。
        while (low<high){
            int min = low;
            int max = low;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i]<arr[min]){
                    min = i;
                }
                if (arr[i]>arr[max]){
                    max = i;
                }
            }
            swap(arr,min,low);
            if (max == low){
                max = min;
            }
            swap(arr,max,high);
            low++;
            high--;
        }
    }

    /**
     * 直接插入排序
     * 已排序区间【0...i）=》默认第一个元素就是已排号序的区间
     * 待排序区间【i...n）
     * @param arr
     */
    public static void insertionSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //已排序区间【0...1）
            //待排序区间【i..n）
            //选择无需区间的第一个元素,不断向前看
            for (int j = i; j >=1&&arr[j]<arr[j-1]; j--) {
                swap(arr,j,j-1);
//                //边界
//                if (arr[j]>arr[j-1]){
//                    //当前无序区间的第一个元素大于有序区间的最后一个元素
//                    break;
//                }else {
//                    swap(arr,j,j-1);
//                }
            }
        }
    }

    /**
     * 二分插入排序
     * @param arr
     */

    public static void insertionSortBS(int[] arr){
        //有序区间【0..i）
        //无序区间【i..n）
        for (int i = 0; i < arr.length; i++) {
            int val=arr[i];
            //有序区间【left...right）
            int left = 0;
            int right = i;
            while (left<right){
                int mid =(left+right)/2;
                if (val<arr[mid]){
                    right = mid;
                }else {
                    //val>=arr[mid]
                   left=mid+1;
                }
            }
            //搬移【left..i）
            for (int j = i; j>left ; j--) {
                arr[j] = arr[j-1];
            }
            //left就是待插入的位置
            arr[left]=val;
        }
    }



    /**
     * 希尔排序 - 缩小增量排序，按照gap将原数组分为gap个子数组，子数组内部先排序，不断缩小gap值，直到gap = 1
     * 当gap = 1时，整个数组已经近乎有序，只需要最后来一次插入排序即可
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap = arr.length>>1;
        // 预处理阶段
        while (gap>=1){
            // 按照gap分组之后，组内进行插入排序
            insertionSortByGap(arr,gap);
            gap=gap>>1;
        }
    }

    /**
     * 大家极端情况，假设此时gap = 1
     * @param arr
     * @param gap
     */
    private static void insertionSortByGap(int[] arr, int gap) {
        // [9,1,2,5,7,4,8,6,3,5] gap = 5
        // i = 5
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j >=gap &&arr[j]<arr[j-gap] ; j-=gap) {
                swap(arr,j,j-gap);
            }
        }
    }



    /**
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length-1);
    }

    /**
     * 迭代实现归并排序(了解)
     * @param arr
     */
    public static void mergeSortNonRecursion(int[] arr) {
        // 最外层循环表示每次合并的子数组的元素个数
        // 子数组为1个元素，第二次循环2个元素，第三次循环合并4个元素，第四次8个元素 ..
        // 直到整个数组合并完成

    }

    /**
     * 在arr[l...r]上进行归并排序
     * @param arr
     * @param l
     * @param r
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        // 2.小数组直接使用插入排
        if (r-l<=15){
            insertionSort(arr,l,r);
            return;
        }
        // int mid = (l + r) / 2;
        // l = 2,r = 4  mid = 3 = 2 + (4 - 2) / 2 = 3
        int mid = l+((r-l)/2);
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid+1,r);
        // arr[l..mid] 和 arr[mid + 1...r]有序 只需要合并这两个子数组即可
        // 1.到底什么时候才需要合并 arr[mid] < arr[mid + 1] 说明？arr[mid] 数组1的最大值 arr[mid + 1]数组2的最小值
        // 整个数组已经有序了，那你还合并个der
        if (arr[mid]>arr[mid+1]){
            // 前后两个子数组还存在乱序，才需要合并
            merge(arr,l,mid,r);
        }
    }
    /**
     * 在arr[l..r]上进行插入排序
     * @param arr
     * @param l
     * @param r
     */
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l+1; i <=r; i++) {
            for (int j = i; j >=l+1&&arr[j]<arr[j-1] ; j--) {
                swap(arr,j,j-1);
            }
        }
    }


    /**
     * 将有序子数组arr[l..mid] 和 有序arr[mid + 1...r] 合并为一个大的有序数组arr[l..r]
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        // 先创建一个新的数组aux,将子数组的值复制给新数组
        int[] aux = new int[r - l + 1];
        // l = 2,r = 4
        // arr[2..4]
        // aux[0..2] 索引下标差了个l偏移量
        for (int i = 0; i < aux.length; i++) {
            // aux的索引下标0...arr.length - 1
            // arr的下标l...r
            aux[i] = arr[i + l];
        }
        // 数组1的开始下标
        int i = l;
        // 数组2的开始下标
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 第一个数组已经遍历完毕
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 第二个子数组遍历完毕
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 将aux[i - l]写回arr[k]
                arr[k] = aux[i - l];
                i ++;
            }else {
                // aux[i - l] > aux[j - l] 写回aux[j - l]
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }

    public static void quickSort(int[] arr) {
        quickSortInternal(arr,0,arr.length - 1);
    }

    public static void quickSortNonRecursion(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        // r
        stack.push(arr.length - 1);
        // l
        stack.push(0);
        // 每次从栈中取出两个元素，这辆个元素就是待排序区间的l..r
        while (!stack.isEmpty()) {
            int l = stack.pop();
            int r = stack.pop();
            if (l >= r) {
                // 当前子数组已经处理完毕
                continue;
            }
            int p = partition(arr,l,r);
            // 继续入栈两个子区间
            stack.push(p - 1);
            stack.push(l);

            stack.push(r);
            stack.push(p + 1);
        }
    }

    private static void quickSortInternal(int[] arr, int l, int r) {
        // 2.小区间上使用插入排序来优化，不用递归到底
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partition(arr,l,r);
        // 继续在左右两个子区间进行快速排序
        // 所有 < v的元素
        quickSortInternal(arr,l,p - 1);
        // 所有 >= v的元素
        quickSortInternal(arr,p + 1,r);
    }

    private static int partition(int[] arr, int l, int r) {
        // 1.优化1.使用一个随机位置作为分区点，避免快排在近乎有序数组上的性能退化
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1..j] < v
        // 最开始区间没有元素
        int j = l;
        // arr[j + 1..i) >= v
        // 最开始大于区间也没有元素
     for (int i = l+1;i<=r;i++){
         if (arr[i]<v){
             swap(arr,i,j);
             j++;
         }
        }
        // 此时元素j就是最后一个 < v的元素，就把v换到j的位置
        swap(arr,l,j);
        return j;
    }

    public static void quickSortHoare(int[] arr) {
        quickSortInternalHoare(arr,0,arr.length - 1);
    }

    private static void quickSortInternalHoare(int[] arr, int l, int r) {
        // 2.小区间上使用插入排序来优化，不用递归到底
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partitionHoare(arr,l,r);
        // 继续在左右两个子区间进行快速排序
        // 所有 < v的元素
        quickSortInternalHoare(arr,l,p - 1);
        // 所有 >= v的元素
        quickSortInternalHoare(arr,p + 1,r);
    }

    /**
     * 挖坑分区法
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partitionHoare(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int pivot = arr[l];
        int i = l;
        int j = r;
        while (i < j) {
            // 先让j从后向前扫描到第一个 < v的元素停止
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            arr[i] = arr[j];
            // 再让i从前向后扫描到第一个 > v的元素停止
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }
    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            boolean isSwaped = false;
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    isSwaped=true;
                }
            }
            if (!isSwaped){
                // 内层没有元素交换，此时整个数组已经有序
                break;
            }
        }
    }


    //原地堆排序
    public static void heapSort(int[] arr){
// 1.先将任意数组进行heapify调整为最大堆
        for (int i = (arr.length-1-1)/2; i >=0; i--) {
            shiftDown(arr,i,arr.length);
        }
        // 2.不断交换堆顶元素到数组末尾，每交换一个元素，就有一个元素落在了最终位置
        for (int i = arr.length-1; i >0; i--) {
            // arr[i] 就是未排序数组的最大值，交换末尾
            swap(arr,0,i);
            shiftDown(arr,0,i);
        }
    }
    private static void swap(int[]arr,int i ,int j ){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }
    private static void shiftDown(int[] arr, int i, int length) {
        while (2*i+1<length){
             int j = 2*i+1;
             if (j+1<length&&arr[j+1]>arr[j]){
                 j=j+1;
             }
             if (arr[i]>arr[j]){
                 break;
             }else {
                 swap(arr,i,j);
                 i=j;
             }
        }
    }
}
